DLOGTIME
外观
在複雜度理論內,DLOGTIME是一個複雜度類,其問題可以用決定型圖靈機,在對數成長的時間內解決。這是使用決定型時間,所能定義出最小且非單純(non-trivial)的複雜度類。這類複雜度一定使用隨機存取圖靈機來定義,因為機器沒有足夠的時間來讀取整個輸入(輸入的大小,成長率是O(n))。
DLOGTIME-均一性(uniformity)在電路複雜性裡面是很重要的。
詢問輸入字串的長度這個問題屬於DLOGTIME,因為我們可以對可能的輸入大小進行折半搜索演算法(binary search)。
易解复杂度类 |
| |||||
---|---|---|---|---|---|---|
怀疑难解复杂度类 |
| |||||
难解复杂度类 | ||||||
复杂度类的谱系 | ||||||
相关复杂度族 |